
#include "BDD.h"


struct vertexSet *insertvertexSet(vertexSet *root,Set *set)
{
		
	struct vertexSet *temp;
	struct vertexSet *v = (struct vertexSet *) malloc (sizeof(struct vertexSet));
	v->s = set;
	v->low = NULL;
	v->high = NULL;

	(temp) = root;
	
	while(temp != NULL)
	{
		if((temp)->s->key1 == set->key1)
		{
			if( set->key2 < (temp)->s->key2 )
			{
				if (temp->low != NULL)
					temp = (temp)->low;
				else
				{	temp->low = v; break; }
			}
			else
			{
				if (temp->high != NULL)
					temp = (temp)->high;
				else
				{	temp->high = v; break;}
			}
		}
		else if( set->key1 < (temp)->s->key1 ){
			if (temp->low != NULL)
					temp = (temp)->low;
				else
				{	temp->low = v; break; }
		}
		else {
			if (temp->high != NULL)
					temp = (temp)->high;
				else
				{	temp->high = v; break;}
		}
	}

	return v;
}


int traverse(vertexSet *v,Set *s,int i)
{
	if(v->low != NULL)
		i = traverse(v->low,s,i);


	s[i].key1 = v->s->key1;
	s[i].key2 = v->s->key2;
	s[i].v = v->s->v;
	i++;
	
	if(v->high != NULL)
		i = traverse(v->high,s,i);
	
	return i;
}

Set *binarySort(Set *set,int j)
{
	vertexSet *root = (vertexSet *) malloc (sizeof(vertexSet));
	Set *temp = (Set*) malloc (sizeof(Set) * j) ;
	int i=1;
	root->s = &(set[0]);
	root->low = NULL;
	root->high = NULL;
	
	
	for(;i<j;i++)
		insertvertexSet(root ,&(set[i]));
	
	traverse(root, temp,0);
	return temp;
}



